import json
import cPickle as pickle
import marshal

def levenshtein_dist(a, b):
    d = list(range(len(a)+1))
    new_d = [0] * (len(a)+1)
    for i in xrange(1, len(b)+1):
        new_d[0] = i
        for j in xrange(1, len(a)+1):
            if j <= len(a) and i <= len(b) and a[j-1]==b[i-1]:
                new_d[j] = d[j-1]
            else:
                new_d[j] = min(d[j]+1, new_d[j-1]+1, d[j-1]+1)
        new_d, d = d, new_d
    return d[len(a)]

def generate_tree():
    f = open(r"pwddict")
    pwddict = f.read().split('\n')
    f.close()

    root = {}
    for i, pwd in enumerate(pwddict):
        node = root
        while True:
            if 0 not in node:
                node[0] = i
                break
            else:
                dist = levenshtein_dist(pwddict[node[0]].lower(), pwd.lower())
                if dist == 0:
                    break
                if dist in node:
                    node = node[dist]
                else:
                    node[dist] = {0:i}
                    break


    f=open(r"pwddict_bktree", 'wb+')
    marshal.dump(root, f)
    f.close()
    print 'okay'


def check_dictionary(pwd, min_dist):
    f=open(r"pwddict_bktree", 'rb')
    root = marshal.load(f)
    f.close()

    f = open(r"pwddict")
    pwddict = f.read().split('\n')
    f.close()

    test_list = [root]
    closest_dist = len(pwd)
    closest_pwd = ""
    checked = 0
    while len(test_list) != 0:
        node = test_list.pop(0)
        node_pwd = pwddict[node[0]]
        dist = levenshtein_dist(node_pwd, pwd)
        checked+=1
        if dist <= closest_dist:
            closest_dist, closest_pwd = dist, node_pwd
        for i in range(max(1,dist-min_dist), dist+min_dist+1):
            if i in node:
                test_list.append(node[i])
    
    if closest_dist < min_dist:
        return closest_dist, closest_pwd
    else:
        return None

generate_tree()   
#print check_dictionary('4r3e2w1qtyuiop', 3)

